package com.data.structure.algorithm.快速排序;

import java.util.Arrays;

/**
 * @Description 快速排序->O(NlogN)  分治+递归的思想
 * @author ll
 * @createTime 2021/6/3  15:58 
 */
public class QuickSort {

	/**
	 * 快速排序
	 * @param arr
	 */
	public static void quickSort(int[] arr,int left,int right){
		if(arr==null||arr.length<2||left>right){
			return;
		}
		int i = left;
		int j = right;
		//选取的基值 最左面的作为基值
		int pivot=arr[i];

		//左面存放的都是比基值小的，右面放的都是比基值大的
		//右面比基值大就一直往左移，直到找到小于基值
		//左面比基值小就一直往右移，直到找到大于基值
		//left与right值交换
		//left最后==right位置就是基值最终的位置

		while(i!=j){
			while(arr[j]>=pivot&&i<j){
				j--;
			}
			while(arr[i]<=pivot&&i<j){
				i++;
			}
			if(i<j){
				int temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
		//交换基值
		arr[left] = arr[i];
		arr[i] = pivot;
		quickSort(arr,left,i-1);
		quickSort(arr,i+1,right);
	}

	/**
	 * 熟悉一下递归，用递归找出数组中最大的数字
	 * @param arr
	 * @return 返回最大的数字
	 */
	public static int findMaxNumber(int[] arr){
		if(arr==null||arr.length==0){
			return Integer.MIN_VALUE;
		}
		if(arr.length==1){
			return arr[0];
		}
		//基线条件
		if(arr.length==2){
			return Math.max(arr[0],arr[1]);
		}
		int head = arr[0];
		int[] ints = Arrays.copyOfRange(arr, 1, arr.length);
		//递归条件
		return Math.max(head,findMaxNumber(ints));
	}

	/**
	 * 递归求数组中元素的和
	 * @param arr
	 * @return
	 */
	public static int getSum(int[] arr){
		if(arr==null||arr.length==0){
			return 0;
		}
		//基线条件
		if(arr.length==1){
			return arr[0];
		}
		int start = arr[0];
		//递归条件
		return start+getSum(Arrays.copyOfRange(arr,1,arr.length));
	}

	/**
	 * 递归求数组中包含的元素个数
	 * @param arr
	 * @return
	 */
	public static int getCount(int[] arr){
		if(arr==null||arr.length==0){
			return 0;
		}
		if(arr.length==1){
			return 1;
		}
		int start = 1;
		return start+getCount(Arrays.copyOfRange(arr,1,arr.length));
	}

	public static void main(String[] args) {
		int[] arr = {1,2,5,7,9,10,3,56,100,35,2,34} ;
		//递归从数组中找最大数
		System.out.println(findMaxNumber(arr));
		//递归求和
		System.out.println(getSum(arr));
		//递归求数组中包含的元素个数
		System.out.println(getCount(arr));

		//快速排序
		quickSort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

}
